"""932. 漂亮数组  https://leetcode.cn/problems/beautiful-array/description/ """


# https://leetcode.cn/problems/beautiful-array/solutions/40197/fen-zhi-fa-by-xue-xi-test/
# 过程中不是漂亮数组，但是最终结果漂亮
def beautifulArray(N: int) -> List[int]:
    # 初始数组
    memory = [list(range(1, N + 1))]

    # 纵向循环
    while True:
        canbreak = True
        new_memory = []
        # 这里需要判断一下，如果当前数组的长度小于等于2，说明已经划分到最小了，直接加入
        # 遍历当前数组（横向循环）
        for item in memory:
            # 这种情况肯定不是漂亮数组，直接加入，同时这里也是循环出口
            if len(item) <= 2:
                new_memory.append(item)
            else:
                # 这里有规律，对于每次的划分内部连续的都不是一个漂亮数组
                # 将item一分为二（奇偶划分）
                new_memory.append(item[0::2])
                new_memory.append(item[1::2])
                # 每次划分了说明了还没有结束
                canbreak = False
        # 看一下可以结束了没，如果上面没有划分说明还没有结束，这里if就是真
        if canbreak:
            break
        else:
            memory = new_memory

    result = []
    for item in memory:
        result.extend(item)
    return result
